#include <assert.h>
#include <stdio.h>
#include <string.h> /* memset */
#include <stdlib.h>
#include <err.h> /* errx */

#include "auxiliar_network.h"
#include "../glib/glist.h"

#define BASE_SIZE 50   /* Tamaño inicial del arreglo de niveles */
#define GROW_FACTOR 2  /* Factor de crecimiento del arreglo de niveles */

#define print_NAprint(...) if(naprint) printf(__VA_ARGS__)

int naprint = 0;

#define PRE_AN_NODE(x) ((x) != NULL && nodeANet_getNode(x) != NULL)
#define PRE_AN_EDGE(x) ((x) != NULL && (x)->e != NULL && (x)->dst != NULL)
#define PRE_AN(x)      ((x) != NULL && (x)->net != NULL && (x)->g != NULL)

/* Prototipos de funciones auxiliares */
static void checkNeighbors(auxNet aNet, nodeANet orig, unsigned int label_t,
                                                     bool fwd);
static auxNet initialize_auxiliarNetwork(network net);
static void realloc_auxiliarNetwork(auxNet aNet);
static GList *auxNet_destroyNodesList(GList *nodes);
static nodeANet auxNetwork_getNodeInLevel(const auxNet aNet,
                              const unsigned int label, unsigned int level);
static void memory_problem(auxNet aNet);


/* Network */
struct sAuxNet{
    network g;           /* Network original */
    GList **net;         /* Arreglo con punteros hacia los niveles del NA */
    unsigned int levels; /* Ultimo nivel ocupado por el network auxiliar */
    unsigned int range;  /* Tamaño del arreglo de niveles */
    nodeANet sink;       /* Puntero a 't' o NULL si todavia no se encontró */
};

auxNet auxNetwork_create(network net, const unsigned int label_s,
                                  const unsigned int label_t){
    nodeANet orig = 0;
    unsigned int sizeLastLevel = 0, i = 0;
    auxNet aNet = NULL;
    GList *lastLevel = NULL;

    assert(net != NULL);

    if(!network_nodeExists(net, label_s)){
        return NULL;
    }

    /* Armo un network por niveles a partir de 'net' */
    aNet = initialize_auxiliarNetwork(net);

    /* Armo el nivel 0 del network auxiliar */
    auxNetwork_addNode(aNet, label_s);
    lastLevel = aNet->net[0];
    sizeLastLevel = g_list_length(lastLevel);
    aNet->levels = 1;

    /* Continuo armando los demás niveles... */

    /* Termino cuando agrego a 't' en el último nivel o cuando no tengo
     * más nodos en el último nivel */
    while((sizeLastLevel > 0) && (aNet->sink == NULL)){
        /* Si llegué a ocupar todos los niveles que tenía disponibles... */
        if(aNet->levels == aNet->range){
            /* Asigno más memoria para el arreglo (sólo si es necesario) */
            realloc_auxiliarNetwork(aNet);
        }
        /* Recorro el último nivel para construir el nivel siguiente */
        for(i = 0; i < sizeLastLevel; i++){
            /* Obtengo un nodo del último nivel */
            orig = g_list_data(lastLevel);

            /* Reviso los vecinos Forward de ese nodo */
            checkNeighbors(aNet, orig, label_t, true);

            /* Reviso los vecinos Backward de ese nodo */
            checkNeighbors(aNet, orig, label_t, false);

            /* Me muevo en el último nivel */
            lastLevel = g_list_next(lastLevel);
        }

        

        /* Reasigno el último nivel al nivel actual */
        lastLevel = aNet->net[aNet->levels];
        sizeLastLevel = g_list_length(lastLevel);
        /* Empiezo a trabajar en el nivel siguiente */
        aNet->levels++;
    }
    /* Network auxiliar creado */
    auxNetwork_print(aNet);

    return aNet;
}

static auxNet initialize_auxiliarNetwork(network net){
    auxNet aNet = (auxNet) malloc(sizeof(struct sAuxNet));
    if(aNet == NULL){
        net = network_destroy(net);
        assert(net == NULL);
        errx(EXIT_FAILURE, "Memoria insuficiente");
    }

    /* Inicializo la estructura del network auxiliar */
    aNet->g = net;
    /* Los niveles arrancan desde 0 en adelante */
    aNet->levels = 0;
    aNet->range = BASE_SIZE;
    aNet->sink = NULL;
    aNet->net = (GList **) calloc(BASE_SIZE, sizeof(GList *));
    if(aNet->net == NULL){
        memory_problem(aNet);
    }
    return aNet;
}

static void realloc_auxiliarNetwork(auxNet aNet){
    /* ...indico en cuanto aumentan los niveles disponibles. */
    aNet->range *= GROW_FACTOR;
    /* ...aumento la cantidad de niveles. */
    aNet->net = realloc(aNet->net, aNet->range * sizeof(GList *));
    if(aNet->net == NULL){
        memory_problem(aNet);
    }

    /* Seteo el nuevo pedazo de memoria que obtuve */
    memset((aNet->net) + aNet->levels, 0,
                             (aNet->range-aNet->levels) * sizeof(GList *));
}

static void checkNeighbors(auxNet aNet, nodeANet orig, unsigned int label_t,
                                                    bool fwd){
    int lvl_dst = 0;
    unsigned int listsize = 0, label_dst = 0, j = 0;
    edge e = NULL;
    nodeANet n = NULL;
    GList *neighbors = NULL;

    /* Vecinos de 'orig' */
    if(fwd){ /* Obtengo los vecinos Forward */
        neighbors = node_getNeighbors(nodeANet_getNode(orig));
    }else{ /* Obtengo los vecinos Backward */
        neighbors = node_getBackwardNeighbors(nodeANet_getNode(orig));
    }
    listsize = g_list_length(neighbors);

    /* Me muevo sobre la lista de vecinos (Forward o Backward) */
    for(j = 0; j < listsize; j++){
        /* Obtengo un vecino */
        e = g_list_data(neighbors);

        /* Chequeo que el lado... */
        if(((!edge_isSaturated(e)) && fwd) || /* ..no sea saturado y forward */
            ((!edge_isEmpty(e)) && !fwd) || /* ..no sea vacío y backward */
            (edge_getCap(e) == 0)){         /* ..que la arista tenga cap(0)
                                             * (ver Decisiones de Diseño) */
            label_dst = node_getLabel(edge_getNeighbor(e));

            /* Averiguo el nivel del vecino 'dst' */
            lvl_dst = node_getLevel(edge_getNeighbor(e));

            /* Si el 'dst' no esta en el network auxiliar... */
            if(lvl_dst == -1){
                /* Agrego el nodo 'dst' al network auxiliar */
                n = auxNetwork_addNode(aNet, label_dst);
                /* Agrego la arista ('orig', 'dst') al network auxiliar */
                nodeANet_addNeighbor(orig, edgeANet_create(e, n, fwd));
            /* Si 'dst' ya estaba en el nivel que estoy computando... */
            }else if(lvl_dst == (int) aNet->levels){
                /* ...obtengo a 'dst' */
                n = auxNetwork_getNodeInLevel(aNet, label_dst, aNet->levels);
                /* Agrego la arista ('orig', 'dst') al network auxiliar */
                nodeANet_addNeighbor(orig, edgeANet_create(e, n, fwd));
            }

            /* Si se encontró el nodo 't'... */
            if(label_dst == label_t){
                /* ...lo agrego al campo 'sink' para terminar la búsqueda. */
                aNet->sink = n;
            }
        }
        /* Avanzo al siguiente vecino */
        neighbors = g_list_next(neighbors);
    }
}

auxNet auxNetwork_destroy(auxNet aNet){
    unsigned int i = 0;

    assert(PRE_AN(aNet));

    /* Destruyo los todos los niveles */
    for(i = 0; i < aNet->levels; i++){
        auxNet_destroyNodesList(aNet->net[i]);
    }
    free(aNet->net);

    /* Reseteo los niveles del network original
     * para poder crear un nuevo network auxiliar */
    network_initializeLevels(aNet->g);

    aNet->g = NULL;
    aNet->sink = NULL;
    free(aNet);
    aNet = NULL;

    return aNet;
}

static GList *auxNet_destroyNodesList(GList *nodes){
    /* Destruyo todos los nodos del nivel */
    g_list_free_full(nodes, (GDestroyNotify) nodeANet_destroy);
    nodes = NULL;

    return nodes;
}

nodeANet auxNet_getSinkNode(const auxNet aNet){
    assert(PRE_AN(aNet));
    return aNet->sink;
}

nodeANet auxNetwork_addNode(auxNet aNet, const unsigned int label){
    nodeANet nANet = NULL;
    unsigned int level = 0;
    node n = NULL;

    assert(PRE_AN(aNet));

    /* Obtengo el nodo asociado a 'label' */
    n = network_getNode(aNet->g, label);
    assert(n != NULL);

    level = aNet->levels;
    /* Creo el nodo en el nivel actual del network auxiliar */
    nANet = nodeANet_create(n, level);
    /* Lo agrego a la lista de nodos del nivel actual */
    aNet->net[level] = g_list_append(aNet->net[level], (gpointer) nANet);

    return nANet;
}

nodeANet auxNetwork_getNode(const auxNet aNet, const unsigned int label){
    nodeANet n = NULL;
    unsigned int i = 0;

    assert(PRE_AN(aNet));

    /* Busco al nodo en todos los niveles del network auxiliar para */
    for (i = 0; i < aNet->levels; i++){
        /* Reviso el nivel i-ésimo */
        n = (nodeANet) auxNetwork_getNodeInLevel(aNet, label, i);
        /* Si lo encontré, lo devuelvo */
        if (n != NULL)
            return n;
    }
    /* El nodo no fue encontrado */
    return NULL;
}

static nodeANet auxNetwork_getNodeInLevel(const auxNet aNet,
                                const unsigned int label, unsigned int level){
    nodeANet n = NULL;
    unsigned int listsize = 0, i = 0;
    GList *nodes = NULL;

    assert(PRE_AN(aNet));
    assert(level <= aNet->levels);

    /* Obtengo la lista de nodos en el nivel 'level' */
    nodes = aNet->net[level];

    if (nodes != NULL){
        listsize = g_list_length(nodes);
        /* Reviso el nivel en busca del nodo */
        for (i = 0; i < listsize; i++){
            /* Obtengo un nodo del nivel */
            n = (nodeANet) g_list_data(nodes);
            /* Si era el que estaba buscando, lo devuelvo */
            if (nodeANet_getLabel(n) == label){
                return n;
            /* Si no era, avanzo al siguiente nodo del nivel */
            }else{
                nodes = g_list_next(nodes);
            }
        }
    }
    /* El nodo no fue encontrado */
    return NULL;
}

edgeANet auxNetwork_getEdge(const auxNet aNet, const nodeANet orig,
                                          const nodeANet dst){
    edgeANet e = NULL;
    nodeANet y = NULL;
    size_t i = 0;
    GList *piv = NULL;

    assert(PRE_AN(aNet));
    assert(PRE_AN_NODE(orig));
    assert(PRE_AN_NODE(dst));

    /* 'piv' se mueve por la lista de vecinos de 'orig' */
    piv = nodeANet_getNeighbors(orig);

    for(i = 0; i < g_list_length(nodeANet_getNeighbors(orig)); i++){
        /* Obtengo una de las aristas de 'orig' */
        e = (edgeANet) g_list_data(piv);
        y = edgeANet_getNeighbor(e);

        /* Si la arista une a 'orig' con 'dst', la devuelvo */
        if(nodeANet_getLabel(y) == nodeANet_getLabel(dst)){
            return e;
        /* Si no, avanzo hacia la siguiente arista */
        }else
            piv = g_list_next(piv);
    }
    /* La arista no fue encontrada */
    return NULL;
}

void auxNetwork_printNodes(const auxNet aNet, unsigned int source){
    unsigned int i = 0, j = 0, length = 0;
    GList *nodes = NULL;

    printf("{%u", source);

    for(i = 0; i < aNet->levels; i++){
        nodes = aNet->net[i+1];

        length = g_list_length(nodes);

        /* Imprimo Los nodos del nivel */
        for(j = 0; j < length; j++){

            printf(", %u",nodeANet_getLabel(g_list_data(nodes)));
            nodes = g_list_next(nodes);
        }

    }
    printf("}\n");

}

void auxNetwork_print(const auxNet aNet){
    unsigned int i = 0, j = 0, length = 0;
    GList *nodes = NULL;
    nodeANet y = NULL;

    assert(PRE_AN(aNet));
    print_NAprint("\n+*************NETWORK AUXILIAR****************+\n");
    print_NAprint("|Total Levels: %u                              |\n",
                     aNet->levels);
    /* Imprimo por niveles */
    for(i = 0; i < aNet->levels; i++){
        print_NAprint("|----------------NALevel: %u-------------------+\n", i);
        nodes = aNet->net[i];
        /* Imprimo Los nodos del nivel */
        length = g_list_length(nodes);
        for(j = 0; j < length; j++){
            y = (nodeANet) g_list_data(nodes);
            nodeANet_print(y);
            nodes = g_list_next(nodes);
        }
    }
    print_NAprint("*---------------------------------------------*\n\n");
}


static void memory_problem(auxNet aNet){
    network net = aNet->g;

    assert(PRE_AN(aNet));

    aNet = auxNetwork_destroy(aNet);
    assert(aNet == NULL);

    net = network_destroy(net);
    assert(net == NULL);

    errx(EXIT_FAILURE, "Memoria insuficiente");
}

